import java.lang.*;

class Principal {

    private static final double phi = (1 + Math.sqrt(5)) / 2;
    private static final double tempoMinimo = 5;
    private static final int repeticions = 3000;
    private static final int anchura = 15;

    public static void main(String[] args) {
        long x;
        double t;
        Crono crono = new Crono();

        //ALGORITMO 1: O(phi^n)
        System.out.println("Algoritmo fib1\n");

        System.out.print(Format.format("n", anchura, true));
        System.out.print(Format.format("T(n)", anchura-8, false));
        System.out.print(Format.format("T(n)/1.1^n", anchura, false));
        System.out.print(Format.format("T(n)/phi^n", anchura, false));
        System.out.println(Format.format("T(n)/2^n", anchura, false));

        for (int j = 0; j < (anchura * 5 - 7); j++) {
            System.out.print("-");
        }
        System.out.println();


        for (int n = 2; n <= 64; n *= 2) {
            boolean bucle = false;

            crono.iniciar();
            x = Fib.fib1(n);
            t = crono.tiempo();

            if (t < tempoMinimo) {
                bucle = true;
                int j;
                double tmp;

                crono.iniciar();
                for (j = 0; j < repeticions; j++) {
                    x = Fib.fib1(n);
                }
                tmp = crono.tiempo();

                t = tmp / repeticions;
            }

            System.out.print(Format.format(String.valueOf(n), anchura, true));
            System.out.print(Format.format((double) t, anchura-9,3) + (bucle ? "*" : " "));
            System.out.print(Format.format(t / Math.pow(1.1, n), anchura, anchura - 3));
            System.out.print(Format.format(t / Math.pow(phi, n), anchura, anchura - 3));
            System.out.println(Format.format(t / Math.pow(2, n), anchura, anchura - 3));
        }
        
        for (int j = 0; j < (anchura * 5 - 7); j++) {
            System.out.print("-");
        }

        
        
        //ALGORITMO 2: O(n)
        System.out.println("\n\nAlgoritmo fib2\n");

        System.out.print(Format.format("n", anchura, true));
        System.out.print(Format.format("T(n)", anchura-8, false));
        System.out.print(Format.format("T(n)/n^0.8", anchura, false));
        System.out.print(Format.format("T(n)/n", anchura, false));
        System.out.println(Format.format("T(n)/n*log(n)", anchura, false));

        for (int j = 0; j < (anchura * 5 - 7); j++) {
            System.out.print("-");
        }
        System.out.println();


        for (int n = 1000; n <= 10000000; n *= 10) {
            boolean bucle = false;

            crono.iniciar();
            x = Fib.fib2(n);
            t = crono.tiempo();

            if (t < tempoMinimo) {
                bucle = true;
                int j;
                double tmp;

                crono.iniciar();
                for (j = 0; j < repeticions; j++) {
                    x = Fib.fib2(n);
                }
                tmp = crono.tiempo();

                t = tmp / repeticions;
            }

            System.out.print(Format.format(String.valueOf(n), anchura, true));
            System.out.print(Format.format((double) t, anchura - 9, 3) + (bucle ? "*" : " "));
            System.out.print(Format.format(t / Math.pow(n, 0.8), anchura, anchura - 3));
            System.out.print(Format.format(t / n, anchura, anchura - 3));
            System.out.println(Format.format(t / (n*Math.log(n)), anchura, anchura - 3));
        }
        
        for (int j = 0; j < (anchura * 5 - 7); j++) {
            System.out.print("-");
        }
        
         //ALGORITMO 3: O(log n)
        System.out.println("\n\nAlgoritmo fib3\n");

        System.out.print(Format.format("n", anchura, true));
        System.out.print(Format.format("T(n)", anchura-8, false));
        System.out.print(Format.format("T(n)/sqrt(log(n))", anchura+5, false));
        System.out.print(Format.format("T(n)/log(n)", anchura, false));
        System.out.println(Format.format("T(n)/n^0.5", anchura, false));

        for (int j = 0; j < (anchura * 5 - 2 ); j++) {
            System.out.print("-");
        }
        System.out.println();


        for (int n = 1000; n <= 10000000; n *= 10) {
            boolean bucle = false;

            crono.iniciar();
            x = Fib.fib3(n);
            t = crono.tiempo();

            if (t < tempoMinimo) {
                bucle = true;
                int j;
                double tmp;

                crono.iniciar();
                for (j = 0; j < repeticions; j++) {
                    x = Fib.fib3(n);
                }
                tmp = crono.tiempo();

                t = tmp / repeticions;
            }

            System.out.print(Format.format(String.valueOf(n), anchura, true));
            System.out.print(Format.format((double) t, anchura-9, 3) + (bucle ? "*" : " "));
            System.out.print(Format.format(t / Math.sqrt(Math.log(n)), anchura+5, anchura - 3));
            System.out.print(Format.format(t / Math.log(n), anchura, anchura - 3));
            System.out.println(Format.format(t / Math.pow(n,0.5), anchura, anchura - 3));
        }
        
        for (int j = 0; j < (anchura * 5 - 2); j++) {
            System.out.print("-");
        }
        
        
        java.util.Date tempoActual = new java.util.Date();
        System.out.println("\n\n(*) Empregouse un bucle de " + repeticions + " iteracions, o tempo reflectido e para unha iteracion");
        System.out.println("Os algoritmos executaronse sobre unha arquitectura " + System.getProperty("os.arch") + " baixo o S.O. " + System.getProperty("os.name") + " version " + System.getProperty("os.version") + ". Coa version " + System.getProperty("java.version") + " de JAVA\n");
        System.out.println("Data: " + tempoActual.toString());
        System.out.println("Todolos tempos en milisegundos");
    }
}